#define min(a,b) ((a>b) ? b : a)

int numSquares(int n){
    int * dp = malloc(sizeof(int) * (n+1));
    dp[0] = 0;
    for(int i=1; i<=n; i++){
        dp[i] = i;
        for(int j=1; i-j*j>=0; j++)
            dp[i] = min(dp[i], dp[i-j*j]+1);
    }
    return dp[n];
}
